<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 1. 统计公平数对的数目
        // 二分查找
        const searchRanage = function (nums, right, target) {
            // 开区间，left初始化为-1，right初始化为nums.length
            let left = -1;
            let mid;
            // 开区间，这里写left + 1 < right
            while (left + 1 < right) {
                mid = left + ((right - left) >> 1)
                if (nums[mid] >= target) {
                    // 是mid，而不是mid-1
                    right = mid
                } else {
                    // 是mid，而不是mid+1
                    left = mid
                }
            }
            // 注意开区间返回的是right
            return right
        }
        /* 
            nums[i]的范围就是[lower - nums[j], upper - nums[j]] 
                lower <= nums[i] + nums[j] <= upper 就是 lower - nums[j] <= nums[i] <= upper - nums[j]
            
            可以转化为 <= upper - nums[j]
            减去 < lower - nums[j]
            
            而
            <= upper - nums[j]的个数 就是 > upper - nums[j]第一个数的下标, 
                而 > upper - nums[j] 可以转化为 >= (upper - nums[j] + 1)
            < lower - nums[j]的个数 就是 >= lower - nums[j]第一个数的下标


            [1, 3, 5, 7, 8, 9]
                <=8的个数，就是求 > 8的第一个数的下标，就是数字9对应的下标5，求>8可以转化为求>=9,所以下面是upper - nums[i] + 1作为target
                <8的个数，就是求 >= 8的第一个数的下标，就是数字8对应的下标4，求>=8就直接把lower - nums[i]传进去
        */
        
        var countFairPairs = function(nums, lower, upper) {
            nums.sort((a, b) => a - b)
            let ans = 0
            for (let j = 0; j < nums.length; j++) {
                // 注意要在[0, j)中二分，题目要求i < j
                let r = searchRanage(nums, j, upper - nums[j] + 1)
                let l = searchRanage(nums, j, lower - nums[j])
                ans += r - l
            }
            return ans
        };
        console.log(countFairPairs([0,1,7,4,4,5], 3, 6), 'countFairPairs');
        console.log(countFairPairs([1,7,9,2,5], 11, 11), 'countFairPairs');
    </script>
</body>

</html>